// 实现前缀树Trie
package Leetcode;

class Trie {
    public Trie[] children;
    public boolean isleaf;

    public Trie() {
        children = new Trie[26];
        isleaf = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            // 如果该节点为空则创建，否则直接经过该前缀
            if (node.children[c - 'a'] == null)
                node.children[c - 'a'] = new Trie();
            node = node.children[c - 'a'];
        }
        // 设置最后一个节点为叶子节点
        node.isleaf = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isleaf == true; // 不为null表示存在前缀，为叶子节点表示长度正好等于word
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    public Trie searchPrefix(String prefix) {
        Trie node = this;
        for (char c : prefix.toCharArray()) {
            if (node.children[c - 'a'] != null)
                node = node.children[c - 'a'];
            else
                return null;
        }
        return node;
    }
}